The invention lies within the general field of information transfer methods. It concerns more particularly a method and device for interleaving data forming part of a transmission or reception method.
The invention finds its place in the general field of the coding of data with a view to their transmission or reception, for example by a radio system. Conventionally there are known in this field coders of the particular type known as xe2x80x9cturbocodersxe2x80x9d (and the associated decoding devices known as xe2x80x9cturbodecodersxe2x80x9d) described for example in previous patents by the same applicant. Such a turbocoder and the associated decoder use one or more data interleaving devices.
The object of the present invention is an interleaving and deinterleaving method, intended to form part of such a so-called xe2x80x9cturbocodingxe2x80x9d method and the associated turbodecoding method.
The present invention applies equally well to the coding of data representing a physical quantity, to the coding of data able to modulate a physical quantity, to the decoding of modulated signals in the form of data, and to the decoding of data representing physical quantities or to the management of data transmissions. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
When convolutional coders are used for implementing an iterative decoding using elementary decoders with soft inputs and outputs, these codes are greatly improved when their coders contain a permutation device, also referred to as an xe2x80x9cinterleaverxe2x80x9d, a permutation device making it possible to return to the initial sequence then being called a xe2x80x9cdeinterleaverxe2x80x9d. In this case, they are normally referred to as turbocoders and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecoderxe2x80x9d. For convenience:
the operation performed by the turbocoder is referred to as xe2x80x9cturbocodingxe2x80x9d, and this operation supplies a so-called xe2x80x9cturbocodedxe2x80x9d sequence
the operation performed by the turbodecoder is referred to as xe2x80x9cturbodecodingxe2x80x9d, and this operation supplies a xe2x80x9cturbodecodedxe2x80x9d sequence.
On these subjects, documents which serve as a reference are, on the one hand, the articles by C. Berrou, A. Glavieux and P. Thitimajshima entitled xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbocodesxe2x80x9d published in the proceedings of the ICC""93 conference, 1993, pages 1064 to 1070, and on the other hand the article by C. Berrou and A. Glavieux entitled xe2x80x9cNear Optimum Error-Correcting Coding and Decoding: Turbocodesxe2x80x9d published in IEEE Transactions on Communications, Volume 44, pages 1261 to 1271, in October 1996.
The aim of the present invention is to propose more efficient interleavers for a turbocoder, that is to say ones making it possible to obtain a greater minimum distance. This is particularly important when the signal to noise ratio of the channel is relatively high, since this can then reduce the decoding error rate and consequently avoid having to send again data wrongly received.
It should be stated briefly here that a turbocode has a different behaviour depending on the value of the signal to noise ratio of the channel. If the signal to noise ratio is high, the minimum weight of the non-zero words of the turbocode and the number of these words of minimum weight predominate in the determination of the performance of the turbodecoder. On the other hand, if the signal to noise ratio is low, it appears that it is the number of code words with a weight close to a value greater than or equal to the minimum weight of the code which influences the performance of the turbodecoder.
The invention relates, in a first aspect, to a permutation method, characterised in that it makes an output rank from 0 to rxc2x7mxe2x88x921 correspond to each input rank from 0 to rxc2x7mxe2x88x921, the said method including the following steps:
E1xe2x80x94a matrix S having r rows and m columns is considered, filled row by row by the successive numbers from 0 to rxc2x7mxe2x88x921,
E2xe2x80x94each column in said matrix S is divided into a predetermined number xcex of sub-columns, such that r/xcex is not prime,
E3xe2x80x94the sub-columns of S equal in number to xcexxc2x7m are designated by Sxcex1xcex2 with 0xe2x89xa6xcex1xe2x89xa6xcexxe2x88x921 and 0xe2x89xa6xcex2xe2x89xa6mxe2x88x921 where xcex2 refers to the column of S where Sxcex1xcex2 appears and xcex1 refers to the position of the sub-column Sxcex1xcex2 in the column of index xcex2.
E4xe2x80x94each sub-column Sxcex1xcex2 is then written in the form of a matrix with R rows and M columns (with r/xcex=RM) and in this form it is interleaved by an interleaver of the so-called xe2x80x9cwheelxe2x80x9d type defined by a circular permutation of each column of said matrix with R rows and M columns, said interleaver not being identity,
E5xe2x80x94this matrix with R rows and M columns is reconverted, after said circular permutations on its columns, into a sub-column S*xcex1xcex2 which will occupy, in a matrix S*, the same position as that occupied by Sxcex1xcex2 in the matrix S,
E6xe2x80x94the permutation table consists of pairs each formed by an element of the matrix S and the element with the same position in the matrix S*.
Preferentially, the method also includes, in at least one column xcex2 (0xe2x89xa6xcex2xe2x89xa6mxe2x88x921) of the matrix S* a modification of the order of appearance of the sub-columns S*xcex1xcex2 in said column.
According to a preferred implementation, one and the same wheel interleaver is used for producing each of the sub-columns S*xcex1xcex2 of a given column xcex2 of the matrix S*.
According to a particular implementation, the sub-columns with at least two columns of the matrix S* are produced by different wheel interleavers.
According to a more particular implementation, the m wheel interleavers used for interleaving the sub-columns in each column of the matrix S* are different.
Preferentially, the method also includes a step of permutation of the columns of S* with each other.
In a particular implementation of the methods described above, the initial matrix S has 2401 elements and is divided into 7 columns of 343 rows, each of these 7 columns itself being divided into 7 sub-columns of 49 elements.
In a preferred embodiment, one chooses: xcex=1. In other words, in this preferred embodiment, when implementing the steps described above, one works with full columns rather than with sub-columns.
To be specific, in this first aspect of the invention, this preferred embodiment relates to a permutation method, causing an output rank from 0 to rxc2x7mxe2x88x921 to correspond to each input rank from 0 to rxc2x7mxe2x88x921, the said method including the followings steps:
E1xe2x80x94a matrix S having r rows and m columns is considered, filled row by row by the successive numbers from 0 to rxc2x7mxe2x88x921,
E2xe2x80x94the m columns of S are designated by Sl with 0xe2x89xa6Ixe2x89xa6mxe2x88x921,
E3xe2x80x94each column Sl is then written in the form of a matrix with R rows and M columns, where R and M satisfy RM=r, and in this form it is interleaved by an interleaver of the so-called xe2x80x9cwheelxe2x80x9d type, defined by a circular permutation of each column in said matrix with R rows and M columns, said interleaver not being identity,
E4xe2x80x94this matrix with R rows and M columns is reconverted, after said circular permutations on its columns, into a column S*l which will occupy, in a matrix S*, the same position as that occupied by Sl in the matrix S,
E5xe2x80x94each column S*l in the matrix S* is permuted by means of a circular permutation,
E6xe2x80x94the permutation table consists of pairs each formed by an element of the matrix S and the element with the same position in the matrix S*.
It will be understood that in this way a permutation table has indeed been created which makes an output rank correspond to each input rank, this permutation table then advantageously being able to be used as a data transfer device, for example using convolutional data turbodecoding.
According to various provisions, possibly used in conjunction, favourable to an effective implementation of this preferred embodiment of the invention:
at least two columns in the matrix S* are obtained by using different wheel interleavers,
the m wheel interleavers used for producing the m columns in the matrix S* are all different,
the method also includes a step of permuting the columns of S* with each other,
during step E5 at least one column S*l in the matrix S* is permuted by means of a circular permutation different from identity.
In a particular implementation of this preferred embodiment, the initial matrix S includes 2415 elements and is divided into 7 columns of 345 rows, each of these 7 columns being itself rewritten in the form of a matrix with 23 rows and 15 columns.
The above-described preferred embodiment of the invention (characterized, to repeat, by xcex=1) is simpler to implement than the general case. Therefore, it will be easier (as described in detail further below) to adjust the various parameters of the coding method according to the invention, in order to obtain a turbocode offering a very low error rate when transmitting coded data.
Returning now to the general case (xcex larger or equal to 1), the invention relates, in a second aspect, to a method of permuting symbols in a sequence of binary data, representing a physical quantity, represented by a polynomial             a      ⁡              (        x        )              =                  ∑                  j          ,          k                    ⁢                        a                      j            ,            k                          ⁢                  x                      jm            +            k                                ,
with binary coefficients, divisible by a first divisor polynomial             g      ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i                    ⁢                      x            i                              +              x        l              ,
with binary coefficients, supplying a new sequence of binary symbols represented by a polynomial                     a        *            ⁡              (        x        )              =                  ∑                  j          ,          k                          xe2x80x83                    ⁢                        a                      j            ,            k                          ⁢                  x                      s                          j              ,              k                        *                                ,
divisible by a second divisor polynomial                     g        *            ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i            *                    ⁢                      x            i                              +              x        l              ,
characterised in that s*j,k is the element in position (j,k) in the matrix S* obtained according to a method as succinctly disclosed above, and m is a multiple of the smallest integer mxe2x80x2 such that the first divisor polynomial g(x) divides xmxe2x80x2+1.
In this second aspect, the invention also relates to a method of permuting the symbols in a sequence of binary data, representing a physical quantity, represented by a polynomial             a      ⁡              (        x        )              =                  ∑                  j          ,          k                    ⁢                        a                      j            ,            k                          ⁢                  x                      jm            +            k                                ,
with binary coefficients, divisible by a first divisor polynomial             g      ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i                    ⁢                      x            i                              +              x        l              ,
with binary coefficients, supplying a new sequence of binary symbols represented by a polynomial                     a        *            ⁡              (        x        )              =                  ∑                  j          ,          k                    ⁢                        a                      s                          j              ,              k                        *                          ⁢                  x                      jm            +            k                                ,
divisible by a second divisor polynomial                     g        *            ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i            *                    ⁢                      x            i                              +              x        l              ,
characterised in that s*j,k is the element in position (j,k) in the matrix S* obtained according to a method as succinctly disclosed above, and m is a multiple of the smallest integer mxe2x80x2 such that the first divisor polynomial g(x) divides xmxe2x80x2+1.
According to a particular embodiment, which procures a simplification in implementation, the second divisor polynomial g*(x) is equal to the first divisor polynomial g(x).
In a third aspect, the invention relates to a coding method characterised in that it includes an operation of determining a sequence a*, during which at least one permutation method as succinctly disclosed above is implemented.
According to a particular implementation of the coding method, working on sequences of binary data u representing information and taking into account a first divisor polynomial             g      ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i                    ⁢                      x            i                              +              x        l              ,
a second divisor polynomial g*(x) compatible with g(x), a first multiplier polynomial f1(x) and a second multiplier polynomial f2(x), an integer number rxe2x89xa71, said method includes:
an operation of forming a xe2x80x9cfirstxe2x80x9d sequence, referred to as xe2x80x9csequence axe2x80x9d, represented by a polynomial a(x) referred to as the xe2x80x9cfirst polynomialxe2x80x9d, whose first rxc2x7mxe2x88x92t coefficients of increasing order are the binary data to be coded and whose last t coefficients are chosen in such a way that the polynomial g(x) divides the polynomial a(x)
an operation of forming a second sequence referred to as xe2x80x9csequence bxe2x80x9d represented by a polynomial b(x) equal to the product of the first polynomial a(x) and the first multiplier polynomial f1(x), the whole divided by the first divisor polynomial g(x),
a permutation operation, working on binary data in the first sequence a in order to form a so-called xe2x80x9cpermutedxe2x80x9d sequence a* represented by a so-called xe2x80x9cpermutedxe2x80x9d polynomial a*(x), whose coefficients of increasing order are the binary data of the permuted sequence a*, and which is divisible by the second divisor polynomial g*(x),
an operation of forming a third sequence referred to as xe2x80x9csequence cxe2x80x9d represented by a polynomial c(x) equal to the product of the permuted polynomial a*(x) and the second multiplier polynomial f2(x), the whole divided by the second divisor polynomial g*(x).
The invention, in this third aspect, also relates to a decoding method implementing at least one permutation method as previously disclosed.
The invention likewise relates to a turbodecoding method using at least one permutation method as previously disclosed.
According to an advantageous arrangement of the methods disclosed above, the alphabet on which the turbocode is defined contains q letters, with q a power of a prime number, the alphabet receiving the structure of the Galois field with q elements.
In a fourth aspect, the invention relates to an interleaver (or permutation device) able to supply, from a sequence a of binary data representing a physical quantity, represented by a polynomial             a      ⁡              (        x        )              =                  ∑                  j          ,          k                    ⁢                        a                      j            ,            k                          ⁢                  x                      jm            +            k                                ,
divisible by a first divisor polynomial g(x), and whose coefficients of increasing order are the binary data of the sequence a, a permuted sequence a* associated with a polynomial a*(x) whose coefficients of increasing order are the binary data of the sequence a*, said polynomial a*(x) being intended to be divided by a second divisor polynomial g*(x) compatible with the first divisor polynomial g(x), in order to form a sequence of binary data c, and a having a number of binary data equal to the product of an integer number r and the integer m, m being a multiple of the smallest integer mxe2x80x2 such that the first divisor polynomial g(x) divides xmxe2x80x2+1,
characterised in that the permuted sequence a* is given by             ∑              j        ,        k              ⁢          xe2x80x83        ⁢                  a                  j          ,          k                    ⁢              x                  s                      j            ,            k                    *                      ,
where the matrix S* with elements s*j,k is produced according to a permutation table creation method as disclosed above.
The invention also relates, in this fourth aspect, to an interleaver adapted to supply, from a sequence a of binary data representing a physical quantity, associated with a polynomial             a      ⁡              (        x        )              =                  ∑                  j          ,          k                    ⁢                        a                      j            ,            k                          ⁢                  x                      jm            +            k                                ,
divisible by a first divisor polynomial g(x), and whose coefficients of increasing order are the binary data of the sequence a, a permuted sequence a* associated with a polynomial a*(x) whose coefficients of increasing order are the binary data of the sequence a*, said polynomial a*(x) being intended to be divided by a second divisor polynomial g*(x) compatible with the first divisor polynomial g(x), in order to form a sequence of binary data c, and a having a number of binary data equal to the product of any integer number r and the integer m, m being a multiple of the smallest integer mxe2x80x2 such that the first divisor polynomial g(x) divides xmxe2x80x2+1 characterised in that the permuted sequence a* is given by             ∑              j        ,        k              ⁢                  a                  s                      j            ,            k                    *                    ⁢              x                  jm          +          k                      ,
where the matrix S* with elements s*j,k is obtained according to a permutation table creation method as disclosed above.
It should be noted here that the interleavers obtained satisfy a property referred to in the remainder of the description as xe2x80x9cReturn to Zeroxe2x80x9d. This means that, when the elementary convolutional coders of the turbocoder are in the null state at the start of the coding of an information sequence, they will both be simultaneously in the null state at the end of the coding of each information sequence.
More precisely, during turbocoding, a sequence is constructed whose polynomial representation a(x) is divisible by a feedback polynomial (also referred to as a divisor polynomial)             g      ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i                    ⁢                      x            i                              +              x        l              ,
of the turbocoder, by simple addition of well-chosen bits equal in number to the degree of the polynomial g(x), at the end of an input sequence u(x). Let a*(x) be the polynomial representation of the interleaved sequence a(x).
It is said that an interleaver satisfies the property of return to zero (RZ) if, each time that a(x) is divisible by g(x), the corresponding polynomial a*(x) is also divisible by g(x). More generally, the case is considered where the two feedback polynomials denoted g(x) and g*(x) (also referred to as first and second divisor polynomials) are not necessarily equal. It is then said that an interleaver satisfies the property RZ if, each time that a(x) is divisible by g(x), the corresponding polynomial a*(x) is divisible by g*(x) The latter definition makes sense only if g(x) and g*(x) have the following property: if       g    ⁡          (      x      )        =            ∏      i        ⁢          (              x        -                  x          i                    )      
is the complete factorisation of g(x) in an extension field of the two-element field, then the complete factorisation of             g      *        ⁡          (      x      )        ⁢      xe2x80x83    ⁢  is  ⁢      xe2x80x83    ⁢            ∏      i        ⁢          (              x        -                  x          i          ϕ                    )      
where xcfx86 is an automorphism (denoted exponentially) of said extension field. Hereinafter such a polynomial g*(x) will be said to be compatible with g(x). In particular, a polynomial is always compatible with itself. It should be noted that two compatible polynomials have the same degree. In addition, if m is the smallest integer such that the first divisor polynomial g(x) divides xm+1, and m* is the smallest integer such that the second divisor polynomial g*(x) divides xm*+1, g*(x) can be compatible with g(x) only if m=m*.
Consider for example the factorisation g(x)=(xxe2x88x92xcex1)(xxe2x88x92xcex12)(xxe2x88x92xcex14) of g(x)=x3+x+1 where xcex1 is a seventh primitive root of the unit and belongs to the field containing eight elements. Consider the six automorphisms xcfx861: xcex1xe2x86x92xcex1i of this eight-element body.
It is verified that xcfx861, xcfx862and xcfx864 produce g*(x)=g(x) whilst xcfx863, xcfx866 and xcfx865 produce g*(x)=x3+x2+1, which is factorised as g*(x)=(xxe2x88x92xcex13)(xxe2x88x92xcex16) (xxe2x88x92xcex15).
The invention also relates to a coding device having an interleaver as briefly disclosed above, and in particular a coding device working on sequences of binary data u representing information and taking into account a first divisor polynomial             g      ⁡              (        x        )              =          1      +                                    ∑                          l              -              1                                            i            =            1                          ⁢                              g            i                    ⁢                      x            i                              +              x        l              ,
a second divisor polynomial g*(x) compatible with g(x), a first multiplier polynomial f1(x) and a second multiplier polynomial f2(x), an integer number rxe2x89xa71, an integer number m which is a multiple of the smallest integer mxe2x80x2 such that the first polynomial g(x) divides xmxe2x80x2+1, characterised in that it has:
means of forming a xe2x80x9cfirstxe2x80x9d sequence, referred to as xe2x80x9csequence axe2x80x9d, represented by a polynomial a(x) referred to as the xe2x80x9cfirst polynomialxe2x80x9d, whose first rxc2x7mxe2x88x92t coefficients of increasing order are the binary data to be coded and whose last t coefficients are chosen in such a way that the polynomial g(x) divides the polynomial a(x)
means of forming a second sequence known as xe2x80x9csequence bxe2x80x9d represented by a polynomial b(x) equal to the product of the first polynomial a(x) and the first multiplier polynomial f1(x), the whole divided by the first divisor polynomial g(x),
permutation means, working on binary data in the first sequence a in order to form a so-called xe2x80x9cpermutedxe2x80x9d sequence a* represented by a so-called xe2x80x9cpermutedxe2x80x9d polynomial a*(x), whose coefficients of increasing order are the binary data of the permuted sequence a*, and which is divisible by the second divisor polynomial g*(x),
means of forming a third sequence known as xe2x80x9csequence cxe2x80x9d represented by a polynomial c(x) equal to the product of the permuted polynomial a*(x) and the second multiplier polynomial f2(x), the whole divided by the second divisor polynomial g*(x).
Likewise, the invention relates to a decoding device using at least one interleaver as disclosed above and/or a deinterleaver corresponding to this interleaver.
The invention also relates to a turbodecoding device using at least one interleaver as disclosed above and/or a deinterleaver corresponding to this interleaver.
The invention also relates to a device employing interleaving and deinterleaving methods like the ones succinctly presented above.
The invention also relates to a data transmission device having a transmitter adapted to use a packet transmission protocol, having a device as disclosed above.
In a particular embodiment, the data transmission device is such that the protocol is the ATM (Asynchronous Transfer Mode) protocol.
In another embodiment, the protocol is the IP protocol (Internet Protocol).
The invention relates more generally to a telephone, a photographic apparatus, a printer, a scanner, a camera, a computer, a facsimile machine, a television receiver and an audio/video player, characterised in that these devices have a device as briefly disclosed above.
The invention also relates to an information storage means and an information storage means which is removable, partially or totally, and which can be read by a computer or microprocessor storing instructions of a computer program, allowing the implementation of the method succinctly disclosed above.